package cn.com.mdx.sort.heapsort;

import cn.com.mdx.sort.SortUtils;

/**
 * <p> 堆排序
 *
 * @author ：huangy
 * @date ：Created in 2020/10/16 5:20 下午
 */
@SuppressWarnings(value = {"rawtypes"})
public class HeapSort {

    /**
     * @param array 要排序的数组
     * @return void
     * @Author huangy
     * @description //TODO 堆排序
     * @date 5:22 下午 2020/10/16
     **/
    public void sort(Comparable[] array) {
        if (array == null || array.length < 1) return;
        int N = array.length - 1;
        //将数组变为二叉堆
        for (int i = N / 2; i >= 1; i--) sink(array, i, N);
        //将数组最大值依次放到数组末尾
        while (N > 1) {
            //收尾交换，将最大值移到数组末尾
            SortUtils.exChange(array, 1, N);
            sink(array, 1, --N);
        }
    }

    /**
     * @param index 要下沉的节点位置
     * @return void
     * @Author huangy
     * @description //TODO 节点下沉
     * @date 10:19 上午 2020/10/16
     **/
    public void sink(Comparable[] array, int index, int N) {
        while (2 * index <= N) {
            //节点index扩大两倍(子节点位置)
            int j = 2 * index;
            if (j < N && SortUtils.less(array[j], array[j + 1])) j = j + 1;
            if (!SortUtils.less(array[index], array[j])) break;
            SortUtils.exChange(array, index, j);
            index = j;
        }
    }

    public static void main(String[] args) {
        Integer[] array = {null, 9, 3, 7, 10, -5, 24, 19, 2, 8, 12, -2};
        SortUtils.printArray(array);
        HeapSort heapSort = new HeapSort();
        heapSort.sort(array);
        SortUtils.printArray(array);
    }

}
